﻿/*
二叉搜索树
	二叉搜索树又叫二叉排序树，他或者是一棵空树，或者是具有以下性质的二叉树
		1.若左子树不为空，则左子树上所有节点的值都小于等于根节点的值
		2.若右子树不为空，则右子树上所有节点的值都大于等于根节点的值
		3.他的左右子树也分别为二叉搜索树
		4.二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，
		  在后续map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset
		  支持插入相等值

理想状态下的时间复杂度：O(logN)           实际时间复杂度：O(N)
								这两个 是O(logN)         log以M为底N   
二叉搜索树 ---> 平衡二叉树 ---> AVL树 ---> 红黑树 ---> B树系列（多叉树）     

哈希表（搜索结构）
数组+排序+二分查找    注：不方便插入删除


二叉搜索树的插入
	插入过程：
		1.树为空，则直接新增节点，赋值给root指针
		2.树不空，按二叉搜索树性质，插入值比当前节点大的往右走，插入值比当前节点小的往左走，找到空位置，插入新节点
		3.如果支持插入相等的值，插入值跟当前节点相等的值可以往右走，也可以往左走，找到空位置，插入新节点。
		  (注意：保持逻辑一致性，插入相等的值不能一会往右,一会往左)
		可以递归也可以循环
	两个指针   一个是记录parent    一个cur


二叉搜索树的查找
	1.从根开始比较，查找x，x比根的值大则往右边查找，x比根值小则往左边查找
	2.最多查找高度次，走到空，若还没找到，那么这个值不存在
	3.如果不支持插入相等的值，找到x就可以返回
	4.如果支持插入相等的值，意味着有多个x的存在，一般要求查找中序的第一个x



二叉搜索树的删除
	首先查找元素是否在二叉搜索树中，如果不存在，就返回false
	如果查找元素存在则分四种情况处理：（假设要删除的节点为N）
		1.要删除节点N左右孩子均为空
		2.要删除的节点N左孩子为空，右孩子节点不为空
		3.要删除的节点N右孩子为空，左孩子节点不为空
		4.要删除的节点N左右孩子节点均不为空

对应四种情况的解决方案
	1.把N节点的父亲对应孩子指针指向空，直接删除N节点（情况1可以当成2或者3处理，效果一样   叶子节点可以归类为情况2/3）
	2.把N节点的父亲对应孩子指针指向N的右孩子，直接删除N节点
	3.把N节点的父亲对应孩子指针指向N的左孩子，直接删除N节点
	4.无法直接删除N节点，因为N的两个孩子无处安放，只能替换法删除。找N左子树的值最大节点R（最右节点）或者N右子树的值
	  最小节点R（最左节点）替代N，因为这两个节点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R
	  的两个节点的值交换，转而变成删除R节点，R节点符合 情况2 或者 情况3，可以直接删除



二叉搜索树key和key/value使用场景
	key搜索场景：
		只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。
		key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key就破坏搜索树结构了。

	key/value搜索场景：
		每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，
		增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树
		支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。



搜索树涉及到一些拷贝和析构的问题
	


*/